package com.ww.springboot.boot.algorithm.string;

import java.util.ArrayList;
import java.util.List;

/**
 * 无重复字符的最长子串
 * <p>
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
 * <p>
 * 解题思路
 * 1.遍历字符串,使用map存储不重复字符串(map 查找会更快，移除也会更快)
 * 2.直到碰到重复字符串 则记录此时list长度,并与之前的长度比较 保留较大的,并丢弃掉list中重复字符之前的字符
 * 3.继续遍历 并重复2操作 直到字符串遍历完成 输出最长长度
 *
 * 解题思路很重要 细节也很重要
 *
 * @author wanwei
 * @since 2021-03-06 10:55
 */
public class LengthOfLongestSubstring2 {

    public static void main(String[] args) {
        String ss = "nfpdmpi";
        System.out.println(method(ss));
    }

    private static int method(String s) {
        int length = 0;
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (list.contains(ch)) {
                int index = list.indexOf(ch);
                for (int j = 0; j <= index; j++) {
                    list.remove(0);
                }
            }
            list.add(ch);
            if (length < list.size()) {
                length = list.size();
            }
        }
        return length;
    }
}
